This invention relates to a packet scheduling device for conducting the scheduling of packet data, and more particularly to, a packet scheduling device for conducting efficiently the scheduling of variable-length packet data with multiple priority classes.
Conventionally, in packet data networks, a variety of service classes are defined according to the kind of traffic, thereby the effective use of resources and the efficient data transfer in the network are achieved. For example, in the Internet service by Internet protocol (IP) there is less need to guarantee its quality of Service (QOS) such as network delay, but in general phone-call service there is need to guarantee the real-time performance. So, the optimum data transfer service of service class according to the kind of traffic is offered, thereby the optimum distribution of resource in the network is achieved.
The service class is defined as a priority class, for example, constant bit rate (CBR), real-time-variable bit rate (rt-VRB) or available bit rate (ABR). CBR is a service optimum to a traffic that requires the real-time performance to guarantee a constant bandwidth always. rt-VRB is a service suitable to a traffic that requires the real-time performance like CBR and the data transfer rate varies. ABR is a service for computer data transmission that does not require the real-time performance but no data loss in the network is allowed.
Users set in advance the priority class to each data flow. Each packet data is, in the packet data network, subject to the data transfer based on requirements such as QOS etc. concerning data discard rate or in-network delay defined according to the each set priority class.
To adapt to such traffic with a variety of priority classes, a packet scheduling device is placed at the post-stage of a packet switch or in the line. The packet scheduling device is provided with a buffer for each priority class, and outputs packet data of each priority class based on a minimum guarantee bandwidth set previously. The packet scheduling in selecting packet data to be output from the buffer provided for each priority class is generally performed by weighted round robin (WRR).
In recent years, the Internet traffic due to the popularization of the Internet increases, therefore it is required to conduct the priority control by packet scheduling to a packet of transmission control protocol/Internet protocol (TCP/IP) used in the Internet. A variety of packet scheduling devices to conduct such priority control have been suggested.
FIG. 1 is a block diagram showing the composition of a conventional packet scheduling device suggested. This packet scheduling device guarantees the bandwidth of each priority class in asynchronous transfer mode (ATM) cell transfer service. In FIG. 1, an ATM cell to the packet scheduling device is input to a queue selection part 11. The ATM cell input is in advance provided with an identifier to indicate the priority class to the header. The queue selection part 11 refers to the header, selects any one of first to M-th queues 121 to 12M provided for each priority class to buffer multiple ATM cells, stores the input ATM cell 10 therein.
From each of the first to M-th queues 121 to 12M, queue length notification signal 13 to indicate the number of ATM cell accumulated is input to an output class selection part 14 and a reset control part 15. Also, first to M-th weight counters 161 to 16M are provided for the first to M-th queues 121 to 12M, respectively, and a weight value corresponding to a bandwidth required to the priority class is in advance set to each of the weight counters. From each of the first to M-th weight counters 161 to 16M, a weight count value 17 as the count result is input to the output class selection part 14 and the reset control part 15.
The class selection part 14 monitors the queue length notification signal 13 from each queue and the weight count value 17 from each weight counter, selects a queue to output cell by the WRR scheduling while referring to priority that the priority class assigned to each queue is further classified into high-priority class or low-priority class. The class selection part 14 sends output allowance signal to the selected queue. The reset control part 15 also monitors the queue length notification signal 13 from each queue and the weight count value 17 from each weight counter, sends reset instruction signal 19 to each of the first to M-th weight counters 161 to 16M when the product of the queue length Qi and weight count value Wi of priority class i becomes xe2x80x9c0xe2x80x9d in all priority classes.
The queue receiving the output allowance signal 18 sent from the class selection part 14 reads its first-accumulated cell of ATM cells stored in the queue, sends it to a cell output part 20. The cell output part 20 outputs the cell to a post-stage device (not shown).
FIG. 2 is a flow chart showing schematically the WRR scheduling processing conducted by this packet scheduling device. In FIG. 2, first, the weight count values set for the respective queues of the first to M-th weight counters 161 to 16M are reset, and a predetermined weight count value for each weight counter is set (step S30). Then, provided that f(i) is the product of queue length Qi and weight count value of each queue, it is judged, in all queues, whether f(i) is xe2x80x9c0xe2x80x9d or not (step S31). If in all queues f(i) is xe2x80x9c0xe2x80x9d (step S31:N), i.e. if the queue length Qi to indicate whether there exists a cell accumulated in the queue is xe2x80x9c0xe2x80x9d, then returns to step S30.
On the other hand, if there exists any cell in any queue and therefore the weight count value Wi is not xe2x80x9c0xe2x80x9d (step S31:Y), then it is judged whether there exists a queue whose priority is classified into high-priority class in priority class with f(i) not xe2x80x9c0xe2x80x9d, or not (step S32). If there exists a queue whose priority class is classified into high-priority class in priority class with f(i) not xe2x80x9c0xe2x80x9d (step S32:Y), then an output class is selected from the judged priority class by WRR (step S33), and the weight count value Wi of the weight counter corresponding to this queue is subtracted by xe2x80x9c1xe2x80x9d (step S34), then returns to step S31.
If there exists no queue whose priority class is classified into high-priority class in priority class with f(i) not xe2x80x9c0xe2x80x9d (step S32:N), then an output class is selected from the judged low-priority class by WRR (step S35), and the weight count value Wi of the weight counter corresponding to this queue is subtracted by xe2x80x9c1xe2x80x9d (step S34), then returns to step S31.
Then, the similar selection processing from step S31 to step S34 is repeated, when f(i) becomes xe2x80x9c0xe2x80x9d in all queues at step S31, the weight count values are reset and are initialized into a predetermined weight value.
Such a method for packet scheduling device is disclosed in, e.g., Japanese patent application laid-open No. 11-68770 (1999) titled xe2x80x9cAn ATM switch scheduling methodxe2x80x9d. By the application of this method, an ATM cell can be output at a bandwidth guaranteed to each priority class according to a weight count value set to each priority class. Also, an ATM cell with high-priority class can be output preferentially without waiting for other ATM cell with low-priority class to be output. Therefore, the delay degradation of traffic in a priority class that requires its real-time performance can be avoided.
Also, Japanese patent application laid-open No. 10-84383 (1998) discloses a packet scheduling device that, as a scheduling key for storing scheduling information to indicate a flow target to be scheduled, one for a packet queue transmittable and one for a packet queue not transmittable are provided separately, and the transmission from the packet queue transmittable is allowed. Thereby, it can be avoided that a same flow continues to be selected until the corresponding counter to each queue becomes unable to make any decrement or a packet queue becomes empty.
However, in the method disclosed in Japanese patent application laid-open No. 11-68770, there is a problem that, due to no consideration of packet length, when the distribution of packet length varies according to priority class, the matching between the weight count value of each weight counter set as a value corresponding to the minimum guarantee bandwidth and the output bandwidth of each priority class may not be obtained. Especially when conducting the packet scheduling of variable-length packet data, it is difficult to determine each weight count value to be set in advance and, when the weight count value is too big, there occurs a problem about transfer delay. On the other hand, when the weight count value is too small, there occurs a problem that, even when there is no priority class to be an output candidate, subsequent packet data cannot be output since the weight count value is negative. Thus, it is difficult to select and output efficiently the variable-length packet data according to the minimum guarantee bandwidth.
In the method disclosed in Japanese patent application laid-open No. 10-84383, although variable-length packet data can be selected and output equally for each queue, to output efficiently variable-length packet data by priority control according to priority class is not disclosed nor suggested.
Accordingly, it is an object of the invention to provide a packet scheduling device that allows variable-length packet data to be selected and output efficiently according to its minimum guarantee bandwidth preset.
According to the invention defined by claim 1 attached herein, a packet scheduling device comprises:
a plurality of packet accumulating means for accumulating one or more variable-length packet with a preset priority class according to each the priority class;
a plurality of weight count means for renewing a weight count value as selection information of priority class every predetermined unit of selection processing, the weight count means being provided corresponding to the plurality of packet accumulating means;
a priority class selecting means for selecting one priority class from priority classes with the weight count value of zero or more in the selection processing according to the round robin to select equally in turn each priority class;
a selection processing repeat-count monitoring means for monitoring a repeat count of the unit of selection processing to be conducted for each priority class;
a renewal instructing means for instructing the plurality of weight count means to renew the weight count value for each priority class so as to allow the weight count value to have zero or more when the repeat count monitored by the selection processing repeat-count monitoring means reaches a predetermined value; and
a packet reading means for reading a variable-length packet accumulated in one of the packet accumulating means corresponding to the priority class selected by the priority class selecting means.
Namely, in the invention defined in claim 1, corresponding to the plurality of packet accumulating means for accumulating multiple variable-length packets with a preset priority class according to said each priority class, the plurality of weight count means for renewing a weight count value as selection information of priority class every predetermined unit of selection processing are provided. One priority class is equally selected from priority classes with the weight count value, as selection information of priority class, of zero or more in the predetermined unit of selection processing according to the round robin to select equally in turn each priority class. However, since a priority class is left out of the selection target if its weight count value is less than xe2x80x9c0xe2x80x9d, when the unit of selection processing reaches a predetermined repeat count, the weight count value of all priority classes is renewed so that the weight count value becomes xe2x80x9c0xe2x80x9d or more. Selecting thus the priority class, the variable-length packet from the corresponding packet accumulating means to the priority class is read by the packet reading means.
According to the invention defined by claim 2 attached herein, a packet scheduling device comprises:
a plurality of packet accumulating means for accumulating one or more variable-length packet with a preset priority class according to the each priority class;
a plurality of weight count means for renewing a weight count value by subtracting a length of variable-length packet when the packet accumulating means output a variable-length packet, and for renewing the weight count value based on a weight value corresponding to minimum guarantee bandwidth of the priority class according to a predetermined renewal instruction signal, the weight count means being provided corresponding to the plurality of packet accumulating means;
a selection processing repeat-count monitoring means for monitoring a repeat count of the unit of selection processing to be conducted for each priority class;
a priority class selecting means for selecting one priority class from priority classes with the weight count value of zero or more in the selection processing according to the round robin to select equally in turn each priority class;
a renewal instructing means for instructing all the plurality of weight count means to renew the weight count value for each priority class so as to allow the weight count value to have a value determined based on the weight value set for each priority class when the repeat count monitored by the selection processing repeat-count monitoring means reaches a predetermined value and the renewed weight count value is less than zero; and
a packet reading means for reading a variable-length packet accumulated in one of the packet accumulating means corresponding to the priority class selected by the priority class selecting means.
Namely, in the invention defined in claim 2, the weight count value is renewed to have a value determined based on the weight value set for each priority class corresponding to the minimum guarantee bandwidth when the repeat count of selection processing reaches a predetermined value and the renewed weight count value is less than zero.
According to the invention defined by claim 3 attached herein, in the packet scheduling device defined by claim 2, the renewal instructing means instructs all the plurality of weight count means to renew the weight count value for each priority class so as to allow the weight count value to have a value of zero or more that is selectable by the priority class selecting means when the repeat count monitored by the selection processing repeat-count monitoring means reaches a predetermined value and the renewed weight count value is less than zero.
Namely, in the invention defined by claim 3, the weight count value is renewed to have a value, which is selectable by the priority class selecting means, set corresponding to the minimum guarantee bandwidth when the repeat count of selection processing reaches a predetermined value and the renewed weight count value is less than zero. Therefore, the selection of priority class can be conducted again by the very simple composition. Thus, the packet scheduling device that the priority class is selected efficiently according to the minimum guarantee bandwidth can be constructed.
According to the invention defined by claim 4 attached herein, the packet scheduling device defined by claim 2 further comprises:
a priority class identifying means for identifying a priority class based on priority class information added in advance to a variable-length packet and for storing the packet into the corresponding packet accumulating means;
wherein the plurality weight count means renews a weight count value by subtracting a length of variable-length packet recognized from packet length information added in advance to a variable-length packet accumulated in corresponding one of the packet accumulating means.
Namely, in the invention defined by claim 4, since information about priority class and packet length, which varies depending on packets, of variable-length packet is directly recognized from additional information of packet, the high-speed processing can be offered by a hardware-formed component.
According to the invention defined by claim 5 or 6 attached herein, the packet scheduling device defined by claim 1 or 2 further comprises:
a repeat-count setting means for setting the predetermined value as a maximum value of the selection processing repeat count.
Namely, in the invention defined by claims 5 and 6, at the maximum value of the selection processing repeat count, the selection of priority class is finished. Therefore, when the selection processing is conducted using a hardware-formed component, the maximum time required for one selection processing can be determined by the maximum repeat count of selection processing. Thus, by varying suitably the maximum repeat count of selection processing according to, for example, gate delay or system-required processing time in LSI (large scale integrated circuit) or large-scale PLD such as FPGA (field programmable gate array), the packet scheduling device using optimally the hardware resource can be constructed.